package Threadprojects.pro3_bestMatching.data.util;

public class EditDistance {
    public static int calculate(String word1, String word2) {
        int m = word1.length();  // 获取第一个字符串的长度
        int n = word2.length();  // 获取第二个字符串的长度

        int[] dp = new int[n + 1];  // 创建一个长度为 n+1 的数组 dp，用于存储动态规划的状态

        // 初始化 dp 数组，dp[j] 表示空字符串到 word2 的前 j 个字符的编辑距离
        for (int j = 0; j <= n; j++) {
            dp[j] = j;
        }

        // 开始动态规划计算编辑距离
        for (int i = 1; i <= m; i++) {
            int prev = dp[0];  // 保存当前行 dp[j-1] 的值
            dp[0] = i;  // 更新 dp[0]，表示从空字符串到 word1 的前 i 个字符的编辑距离
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];  // 保存当前 dp[j] 的值
                // 根据 word1 的第 i 个字符和 word2 的第 j 个字符是否相等来更新 dp[j]
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = prev;  // 如果相等，则当前 dp[j] 等于上一行 dp[j-1] 的值
                } else {
                    // 如果不相等，则取插入、删除、替换操作中的最小值，并加上相应的操作次数
                    dp[j] = Math.min(prev + 1, Math.min(dp[j] + 1, dp[j - 1] + 1));
                }
                prev = temp;  // 更新 prev，将当前 dp[j] 的值赋给 prev，用于下一次循环
            }
        }

        return dp[n];  // 返回最终的编辑距离，即 dp[n] 的值
    }

    private static int minimum(int a,int b,int c){
        return Math.min(Math.min(a,b),c);
    }

    public static int calculate1(String src,String dst){
        int[][] distance = new int[src.length() + 1][dst.length() + 1];

        for (int i = 0;i <= src.length();i++) {
            distance[i][0] = i;
        }
        for (int j = 0;j <= dst.length();j++) {
            distance[0][j] = j;
        }

        for (int i = 1;i <= src.length();i++){
            for (int j = 1;j <= dst.length();j++){
                int flag = (src.charAt(i - 1) == dst.charAt(j - 1)) ? 0 : 1;
                distance[i][j] = minimum(
                        distance[i - 1][j] + 1,
                        distance[i][j - 1] + 1,
                        distance[i - 1][j - 1] + flag);
            }
        }
        return distance[src.length()][dst.length()];
    }
}

